package chapter02;

import java.util.Arrays;

public class NumDecodings91 {
    /**
     * 记忆化搜索
     * process(chs,pos) 尝试chs[pos]组成数字的可能性
     * 递归出口
     * 1).pos==length-1
     *  之前尝试都合法并且已经到达最后位置 返回一种可能
     *  return 1
     * 2).chs[pos]=='0'  后续尝试都不合法
     *  return 0
     * 3).当前位置可以考虑
     *  a).当前字符单独作为一个数
     *    int res=process(chs,pos+1)
     *  b).当前字符和后一个字符作为一个数
     *    pos+1<length&&([pos]=='1'||[pos]=='2'&&[pos+1]>='0'&&[pos+1]<='6')
     *    res+=process(chs,pos+2)
     * 递归过程会产生重复解 增加缓存dp[pos] 提高效率
     */
    public int numDecodings(String s) {
        char[] chs=s.toCharArray();
        int[] dp=new int[chs.length+1];
        Arrays.fill(dp,-1);
        return process(chs,0,dp);
    }

    public int process(char[] chs,int pos,int[] dp){
        if(dp[pos]!=-1){
            return dp[pos];
        }
        if(pos==chs.length){
            dp[pos]=1;
            return dp[pos];
        }
        if(chs[pos]=='0'){
            dp[pos]=0;
            return dp[pos];
        }
        int res=0;
        res=process(chs,pos+1,dp);
        if(pos+1<chs.length){
            if(chs[pos]=='1'||chs[pos]=='2'&&chs[pos+1]>='0'&&chs[pos+1]<='6'){
                res+=process(chs,pos+2,dp);
            }
        }
        dp[pos]=res;
        return dp[pos];
    }

    //动态规划
    public int numDecodings1(String s) {
        char[] chs=s.toCharArray();
        int N=chs.length;
        int[] dp=new int[N+1];
        dp[N]=1;
        for (int i=N-1;i>=0;i--){
            if(chs[i]=='0'){
                dp[i]=0;
                continue;
            }
            dp[i]=dp[i+1];
            if(i+1<chs.length&&(chs[i]=='1'||chs[i]=='2'&&chs[i+1]>='0'&&chs[i+1]<='6')){
                dp[i]+=dp[i+2];
            }
        }
        return dp[0];
    }
}
